package com.love.dynamicPlan;


/**
 * 假设有排成一行的N个位置，记为 1 ~ N，N一定大于或等于 2
 * 开始时机器人在其中的M位置上（M一定是 1-N 中的一个）
 * 如果机器人来到 1 位置，那么下一步只能往左到 2 位置；
 * 如果机器人来到 N 位置，那么下一步只能来到 N - 1 位置
 * 如果机器人来到中间位置，那么下一步可以往左走 或者 往右 走
 * 规定机器人必须走 K 步，最终能来到 P 位置 （P 也是 1 ~ N 中的一个 ）的方法有多少种
 * 给定四个参数 N,M,K,P,返回方法数（走到P这个地方一共有多少种走法）
 */



public class RoadTimes {



    public static int way1(int N,int start,int aim,int K){
        return process1(start,K,aim,N);
    }

    /**
     *
     * @param cur : 机器人当前来到的位置是cur
     * @param rest : 机器人还有rest步需要去走
     * @param aim : 最终目标是aim
     * @param N : 有哪些位置？ 1 ~ N
     * @return 机器人从 cur 出发，走过 rest 步之后，最终停在 aim 的方法数，是多少
     */
    public static int process1(int cur,int rest,int aim,int N){
        if(rest == 0){ // 如果已经不需要走了，走完了
            return cur == aim ? 1 : 0;
        }
        // rest > 0,还有步数要走
        if(cur == 1){
            // 1 位置到 aim 的方法数，等于 2 位置到 aim 的方法数
            return process1(2,rest - 1,aim,N);
        }
        if (cur == N){
            return process1(N - 1,rest - 1,aim,N);
        }
        // 机器人
       return process1(cur - 1,rest -1 ,aim ,N) + process1(cur + 1,rest - 1,aim,N);
    }







    /*********************************************************************************************/

    /**
     *
     * @param N
     * @param start
     * @param aim
     * @param K
     * @return
     */
    public static int way2(int N,int start,int aim,int K ){
        int[][] dp = new int[N+1][K+1];
        for (int i = 0; i <= N ; i++) {
            for(int j = 0; j <= K; j++){
                dp[i][j] = -1;
            }
        }

        return process(start,K,aim,N,dp);
    }


    // cur 当前位置 范围： 1 ~ N
    // rest 剩余步数 范围： 0 ~ K
    public static int process(int cur,int rest, int aim,int N,int[][] dp){
        if(dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        // 之前没算过
        int ans = 0;
        if(rest == 0){
            ans = cur == aim ? 1 : 0;
        }else if(cur == 1) {
            ans = process(2,rest - 1,aim,N,dp);
        }else if(cur == N){
            ans = process(N - 1,rest - 1,aim,N,dp);
        }else {
            ans = process(cur - 1,rest - 1,aim,N,dp) + process(cur + 1,rest - 1,aim,N,dp);
        }
        dp[cur][rest] = ans;

        return ans;
    }


    public static void main(String[] args) {
//        System.out.println(way2(4,2,4,4));

        System.out.println(way1(5,2,4,4));

    }



}
